КОМБИНАТОРНЫЕ ЗАДАЧИ ПО ГЕОМЕТРИИ

Одной из первых аксиом геометрии, относящейся к взаимному расположению точек и прямых на плоскости, является аксиома о том, что через любые две точки плоскости проходит единственная прямая.

Задача 1. Сколько прямых проходит через различные пары из: а) трех точек; б) четырех точек; в) пяти точек; г) n точек, никакие три из которых не лежат на одной прямой?

Решение. Пусть даны точки A₁, …, A_n. Выясним, сколько прямых проходит через точку A₁ и оставшиеся точки. Так как число оставшихся точек равно n – 1 и через каждую из них и точку A₁ проходит одна прямая, то искомое число прямых будет равно n – 1. Заметим, что рассуждения, проведенные для точки A₁, справедливы для любой точки. Поскольку всего точек n и через каждую из них проходит n – 1 прямая, то число посчитанных прямых будет равно n(n – 1). Конечно, этот ответ, который могут дать учащиеся, не является верным. Например, при n = 3 получаем n(n – 1) = 6, а число прямых на самом деле равно 3. Хорошо, если учащиеся сами догадаются, что при указанном выше подсчете мы каждую прямую посчитали дважды и поэтому число прямых, проходящих через различные пары из n данных точек, равно .

Полученная формула числа прямых имеет большое значение, в дальнейшем будет появляться при решении различных комбинаторных задач. Поскольку каждая прямая однозначно задается двумя точками, мы, по существу, вычислили, сколько различных пар можно составить из n элементов. При этом не имеет значение, какие это элементы. Число таких пар называется числом сочетаний из n элементов по два и обозначается . Например, если в классе 20 учеников, то число различных пар, которые можно образовать из учеников этого класса, равно  = 190.

Следующая серия задач связана с числом попарных пересечений прямых на плоскости. Из сформулированной выше аксиомы непосредственно следует, что две прямые могут иметь не более одной общей точки.

Задача 2. Какое наибольшее число точек попарных пересечений могут иметь: а) три прямые; б) четыре прямые; в) пять прямых; г) n прямых?

Решение. Заметим, что наибольшее число точек попарных пересечений получается, если каждая прямая пересекается с каждой, и при этом никакие три прямые не пересекаются в одной точке. В этом случае каждая прямая имеет n – 1 точку пересечения с остальными прямыми, и мы находимся в ситуации, аналогичной ситуации задачи 1. Так как всего прямых n, и на каждой прямой n – 1 точка, то их общее число будет равно n(n – 1). При этом, поскольку каждую точку мы подсчитали дважды, число точек пересечения будет равно .

Можно было бы рассуждать и короче. Действительно, для того, чтобы подсчитать количество точек пересечения, достаточно подсчитать, количество пар прямых, которые можно образовать из данных n прямых. Как мы знаем, это число равно  .

Обратим внимание на то, что формулировка и решение задачи 2 похожи на формулировку и решение задачи 1. Действительно,  переформулируем утверждения этих задач.

Утверждение 1. Число прямых, проходящих через различные пары из n точек, никакие три из которых не лежат на одной прямой, равно .

Утверждение 2. Число точек попарных пересечений n попарно пересекающихся прямых, никакие три из которых не пересекаются в одной точке, равно .

Мы видим, что если слово "прямая" в утверждении 1 заменить на слово "точка", слово "точка" – на слово "прямая", прохождение прямой через две точки заменить на пересечение двух прямых, и принадлежность трех точек прямой – на пересечение трех прямых в одной точке, то получим утверждение 2. Это же относиться и к доказательствам этих утверждений. Одно получается из другого указанной выше заменой. Такая аналогия называется двойственностью между точками и прямыми.

Еще одной аксиомой, относящейся к взаимному расположению прямых на плоскости, является аксиома о том, что прямая разбивает плоскость на две части. При этом, если две точки принадлежат разным частям, то отрезок, соединяющий эти точки, пересекается с прямой, а если точки принадлежат одной части, то отрезок, их соединяющий, не пересекается с прямой.

Задача 3. На сколько частей разбивают плоскость: а) две прямые; б) три прямые; в) четыре прямые; г) n прямых, пересекающиеся в одной точке?

Ответ. 2n.

Задача 4. На сколько частей разбивают плоскость n попарно пересекающихся прямых, никакие три из которых не пересекающиеся в одной точке?

Решение. Выясним, на сколько увеличивается число частей плоскости при добавлении новой прямой к данным. Это увеличение происходит за счет того, что какие-то части плоскости разбиваются новой прямой на меньшие части. Так, если имелось две пересекающиеся прямые, то при добавлении третьей прямой три из имеющихся четырех частей плоскости разбиваются на две части и общее число образованных частей равно 7 = 4 + 3. Заметим, что количество частей плоскости, которые разбиваются на две части новой прямой, равно количеству частей новой прямой, на которые она разбивается точками пересечения с имеющимися прямыми. Каждая такая часть новой прямой разбивает соответствующую часть плоскости на две части. Поскольку n-я прямая пересекается с n – 1 прямой, то она разбивается на n частей и поэтому число частей плоскости увеличивается на n. Таким образом, общее число частей, на которые n  прямых разбивают плоскость, равно 4 + 3 + … + n.

Нахождение формулы для этой суммы может быть проведено чисто геометрическими методами. Укажем на один из них, позволяющий найти сумму 1 + 2 + … + n.

Рассмотрим квадрат (n + 1) x (n + 1). Число его клеток равно (n + 1)². Подсчитаем эти клетки по диагоналям. В первой диагонали имеется одна клетка. Во второй диагонали – 2. И так далее, в n-ой диагонали – n. Таким образом, общее число клеток в диагоналях, расположенных ниже (n + 1)– ой (большой) диагонали, равно 1 + 2 + … + n. Аналогично, общее число клеток в диагоналях, расположенных выше (n + 1)– ой (большой) диагонали, равно 1 + 2 + … + n. Поскольку в большой диагонали (n + 1) клеток, то общее число клеток в квадрате, подсчитанное по диагоналям равно 2(1 + 2 + … + n) + (n + 1). Следовательно, имеем равенство 2(1 + 2 + … + n) + (n + 1) = (n + 1)², из которого получаем

Используя эту формулу, находим искомое число частей 4 + 3 +… + n =